package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

https://leetcode.cn/problems/combination-sum/description/
https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []
 */
class leetcode_39 {
    @Test
    fun test_1() {
        val array = BooleanArray(3)
        val actual = combinationSum(intArrayOf(2, 3, 6, 7), 7)
        val expect = arrayListOf(arrayListOf(2, 2, 3), arrayListOf(7))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual = combinationSum(intArrayOf(2, 3, 5), 8)
        val expect = arrayListOf(arrayListOf(2, 2, 2, 2), arrayListOf(2, 3, 3), arrayListOf(3, 5))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_3() {
        val actual = combinationSum(intArrayOf(2), 1)
        val expect = ArrayList<ArrayList<Int>>()
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
        /*
            回溯法
            注意：
            1 元素可以重复
            2 先排序
         */
        // TODO: sort()
        candidates.sort()
        val path: ArrayList<Int> = ArrayList<Int>()
        val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        backtracking(candidates, target, 0, 0, path, result)
        return result
    }

    fun backtracking(candidates: IntArray, target: Int, sum: Int, startIndex: Int, path: ArrayList<Int>, result: ArrayList<ArrayList<Int>>) {
        // 结束条件
        if (candidates.isEmpty()) {
            return
        }
        // 剪枝操作1
        // if(sum > target){
        //     return
        // }

        if (sum == target) {
            // 收集数据
            val items: ArrayList<Int> = ArrayList<Int>()
            items.addAll(path)
            result.add(items)
            return
        }

        for (i in startIndex..candidates.size - 1) { // [startIndex, end index]
            val tempSum: Int = sum + candidates[i]
            // 剪枝操作1
            if (tempSum > target) {
                return
            }
            // 处理逻辑
            path.add(candidates[i])

            //  递归
            // println("for, sum + candidates[i] = $sum + ${candidates[i]}")
            // 因为元素可以重复，start 为 i，不是i+1
            backtracking(candidates, target, tempSum, i, path, result)

            // 回溯
            path.removeAt(path.size - 1)
        }
    }
}